/*
 * @Descripttion: 234. 回文链表
 * https://leetcode.cn/problems/palindrome-linked-list/
 * @Author: yubo
 * @Date: 2022-09-26 15:37:58
 * @LastEditTime: 2022-09-26 16:05:57
 */
#pragma once

#include "../Base/ListNode.h"

#include <stack>

namespace Solution_234
{
    class Solution
    {
    public:
        bool isPalindrome(ListNode *head)
        {
            if(head == nullptr)
                return false;

            int total = Length(head);
            bool isOdd = (total % 2 != 0);
            int mid = total / 2;

            stack<int> cache;

            int cnt = 0;
            ListNode *lIter = head;
            while (lIter != nullptr)
            {
                ++cnt;
                if (cnt <= mid)
                {
                    cache.push(lIter->val);
                }
                else
                {
                    if(cnt == mid + 1 && isOdd)
                    {
                        ;
                    }
                    else
                    {
                        int curr = cache.top();
                        if(curr != lIter->val)
                        {
                            return false;
                        }
                        cache.pop();
                    }
                }
                
                lIter = lIter->next;
            }
            return true;
        }

    private:
        int Length(ListNode* head)
        {
            ListNode *lIter = head;
            int length = 0;
            while (lIter != nullptr)
            {
                ++length;
                lIter = lIter->next;
            }
            return length;
        }
    };

    void Test()
    {
        vector<int> vec{1, 2};
        ListNode *head = AssignListNode(vec);

        Solution solv;
        cout << boolalpha << solv.isPalindrome(head) << endl;
    }
}